/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 25
 * Time: 16:20
 */
//牛客 寻找峰值
public class Solution4 {
    //法一 我的方法 时间复杂度为O(n)
    public int findPeakElement (int[] nums) {
        if(nums.length == 1) return 0;
        if(nums[0] > nums[1]) return 0;
        if(nums[nums.length - 1] > nums[nums.length - 2]) return nums.length - 1;
        for(int i = 1; i < nums.length - 1; i++) {
            if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }else {
                i++;
            }
        }
        return -1;
    }

    //法二 根据官方思路我写的代码
    public int findPeakElement1 (int[] nums) {
        if(nums.length == 1) return 0;
        if(nums[0] > nums[1]) return 0;
        if(nums[nums.length - 1] > nums[nums.length - 2]) return nums.length - 1;
        return findPeakElementF(nums, 1, nums.length - 2);
    }
    public int findPeakElementF(int[] nums, int left, int right) {
        if(left >= right) return left;
        int mid = (left + right) / 2;
        int mid1 = findPeakElementF(nums, left, mid);
        int mid2 = findPeakElementF(nums, mid + 1, right);
        if(mid1 >= 1 && nums[mid1] > nums[mid1 - 1] && nums[mid1] > nums[mid1 + 1]) {//递归在归时有可能带回-1赋值给mid1，此时nums[mid1-1]会越界，所以条件要加上mid1>=1
            return mid1;
        }else if(mid2 >= 1 && nums[mid2] > nums[mid2 - 1] && nums[mid2] > nums[mid2 + 1]) {
            return mid2;
        }
        return -1;
    }

    //法三 官方方法
    public int findPeakElement2 (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] < nums[mid + 1]) {//用mid+1，因为用mid-1当mid是0时会发生数组越界，mid因为(left+right)/2的精度问题会造成mid向更左边的位置偏移，mid此时有可能为0
                left = mid + 1;
            }else if(nums[mid] > nums[mid + 1]) {//因为要往高趋势走，nums[mid]比右边的大（自己较大）则right=mid，nums[mid]比右边的小（自己较小）则left=mid+1
                right = mid;
            }
        }
        return right;
    }
}
